package com.leecode.xiehf.page_01;

import java.util.Arrays;

/**
 * 编写一个程序，通过填充空格来解决数独问题。
 * <p>
 * 一个数独的解法需遵循如下规则：
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 * 空白格用 '.' 表示。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sudoku-solver
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0037 {

    public static void main(String[] args) {
        Solution_0037 solution = new Solution_0037();
        char[][] board = {
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
        solution.solveSudoku(board);
        System.out.println(Arrays.deepToString(board));
    }

    public void solveSudoku(char[][] board) {
        // 行  位置与数字存在标识
        boolean[][] line = new boolean[9][9];
        // 列  位置与数字存在标识
        boolean[][] column = new boolean[9][9];
        // 3x3 位置与数字存在标识
        boolean[][] table = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    line[i][num] = true;
                    column[j][num] = true;
                    // [
                    //  [0, 1, 2]
                    //  [0, 1, 2]
                    //  [0, 1, 2]
                    // ]
                    table[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        dfs(board, line, column, table, 0, 0);
    }

    private boolean dfs(char[][] board,
                        boolean[][] line,
                        boolean[][] column,
                        boolean[][] table,
                        int i, int j) {
        // 找到下一个没有填数字的位置
        while (board[i][j] != '.') {
            if (++j >= 9) {
                i++;
                j = 0;
            }
            if (i >= 9) {
                return true;
            }
        }
        for (int num = 0; num < 9; num++) {
            int tableIndex = i / 3 * 3 + j / 3;
            if (!line[i][num]
                    && !column[j][num]
                    && !table[tableIndex][num]) {
                // 如果3个方向都不存在这个数值，就把这个数加到对应位置
                board[i][j] = (char) ('1' + num);
                line[i][num] = true;
                column[j][num] = true;
                table[tableIndex][num] = true;
                if (dfs(board, line, column, table, i, j)) {
                    return true;
                } else {
                    board[i][j] = '.';
                    line[i][num] = false;
                    column[j][num] = false;
                    table[tableIndex][num] = false;
                }
            }
        }
        return false;
    }
}

